package medium

import (
	. "GoLeetcode/common"
)

/*
时间复杂度：O(n*(m+n))
空间复杂度：O(n)

TODO:其他解法？？ floyd/dijkstra
https://leetcode-cn.com/problems/network-delay-time/solution/gong-shui-san-xie-yi-ti-wu-jie-wu-chong-oghpz/
*/

func networkDelayTime(times [][]int, n int, k int) int {
	dist := make([]int, n+1)
	for i := 1; i < n+1; i++ {
		dist[i] = INF
	}
	dist[k] = 0
	// 最多经过n-1条边
	for limit := 0; limit < n-1; limit++ {
		// 注意1：这一步一定不能漏了，当前这一步由上一步的结果推导而来
		clone := make([]int, n+1)
		copy(clone, dist)
		for _, v := range times {
			from, to, d := v[0], v[1], v[2]
			dist[to] = Min(dist[to], clone[from]+d)
		}
	}

	// 注意2：这一步也不能忘了，当>=INF时，说明不可达，需要返回-1
	result := Max(dist[1:]...)
	if result >= INF {
		return -1
	}
	return result
}
